Mobile ad-hoc networks (MANET's) are becoming increasingly popular because they operate as self-configuring networks of mobile routers or associated hosts connected by wireless links to form an arbitrary topology. The routers, such as wireless mobile units, can move randomly and organize themselves arbitrarily as nodes in a network, similar to a packet radio network. The individual units require minimum configuration and their quick deployment can make ad-hoc networks suitable for emergency situations. For example, many MANET's are designed for military systems such as the JTRS (Joint Tactical Radio System) and other similar peer-to-peer or Independent Basic Service Set Systems (IBSS).
TDMA technology is becoming more popular for use in these mobile ad-hoc network systems. In a TDMA ad-hoc network, channel access scheduling is a core platform of the network structure. Some problems, however, are encountered with distributed channel scheduling used in a multi-hop broadcast networks. As known to those skilled in the art, the optimum channel scheduling problem is equivalent to the graph coloring problem, which is a well known NP-complete problem, cited in numerous sources. Many prior art systems assume that the network topology is known and is not topology transparent.
There is a changing topology in a TDMA ad-hoc network. Before the network is formed, the topology cannot be learned. Without knowing the network topology, the nodes in the network should still find a way to communicate. Once the nodes learn about the transmit and receive schedules among neighboring nodes, these neighboring nodes may have moved away, disappeared, or new nodes may have moved in. The rate of resolving the scheduling must be fast and bandwidth efficient such that the network can be stabilized.
In a dynamic ad-hoc network system, fault tolerance and load balancing is important because radio links in the path can break. In such cases, broken links should be detected and new paths set-up, This overhead could disrupt the voice or data steams. In some cases, the network may be busy and cannot set up new paths and bring down the old paths, leaving no time or capacity for the actual data delivery.
The radio link stability is also a factor in path maintenance or overhead. Fault tolerance, for example, could help maintain the data path in service much longer and better. Load balancing would help increase the overall data throughput, or equivalently, reduce the traffic burden on certain links.
There are some current solutions, however, that reduce these problems. In a hop-to-hop system, a data packet is transmitted based on local hop-to-hop routing decisions. In this system, there is usually no obligation for the nodes to guarantee the delivery of a data packet to the next hop. Sending duplicates over multiple links (locally decided), however, could be used. This is considered a solution for the fault tolerance. But the drawback is that the same data packet must be sent over many branches, eventually leading to partial or complete flooding of the packet in the network, causing unnecessary duplicates of the packet.
A path local repairs system can be a solution to the above hop-to-hop flooding problem. In this system, a path is established for the data delivery, but in the wireless networks, the topologies change and the established path may not be valid any more over time because the links may be gone. To fix the problem, a locally initiated repair mechanism (local repair) can be used to rescue the path. This is an adequate solution, but has some drawbacks because it takes time to detect the broken links and find a reroute path to the downstream of the path.
A multiple path, fully disjoint (FD), or partial disjoint (PD) solution is another system. The multiple paths used for the duplicated data packets can be created for redundancies in delivery. The paths, however, still need to be maintained. Also, some bandwidth is wasted because of path redundancies. In the PD system, the data traffics are merged at the critical region of the data paths. A critical region is the part that the nodes or the link share among the data paths. There could also be an extra burden of traffic in the critical regions.